/*
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

/*
 *
 *
 *
 *
 *
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util.concurrent.locks;
import java.util.concurrent.TimeUnit;
import java.util.Collection;

/**
 * 总结：
 * 1. 重入锁是指可重复获取的锁，即一个线程获取锁之后再尝试获取锁时会自动获取锁；
 * 2. 在ReentrantLock中重入锁是通过不断累加state变量的值实现的；
 * 3. ReentrantLock的释放要跟获取匹配，即获取了几次也要释放几次；
 * 4. ReentrantLock默认是非公平模式，因为非公平模式效率更高；
 * 5. 条件锁是指为了等待某个条件出现而使用的一种锁；
 * 6. 条件锁比较经典的使用场景就是队列为空时阻塞在条件notEmpty上；
 * 7. ReentrantLock中的条件锁是通过AQS的ConditionObject内部类实现的；
 * 8. await()和signal()方法都必须在获取锁之后释放锁之前使用；
 * 9. await()方法会新建一个节点放到条件队列中，接着完全释放锁，然后阻塞当前线程并等待条件的出现；
 * 10. signal()方法会寻找条件队列中第一个可用节点移到AQS队列中；
 * 11. 在调用signal()方法的线程调用unlock()方法才真正唤醒阻塞在条件上的节点（此时节点已经在AQS队列中）；
 * 12. 之后该节点会再次尝试获取锁，后面的逻辑与lock()的逻辑基本一致了。
 */
public class ReentrantLock implements Lock, java.io.Serializable {
    private static final long serialVersionUID = 7373984872572414699L;

    /** 它在构造方法中初始化，决定使用公平锁还是非公平锁的方式获取锁 */
    private final Sync sync;

    /**
     * 抽象类Sync实现了AQS的部分方法
     */
    abstract static class Sync extends AbstractQueuedSynchronizer {
        private static final long serialVersionUID = -5179523762034025860L;

        /**
         * Performs {@link Lock#lock}. The main reason for subclassing
         * is to allow fast path for nonfair version.
         */
        abstract void lock();

        /**
         * Performs non-fair tryLock.  tryAcquire is implemented in
         * subclasses, but both need nonfair try for trylock method.
         */
        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                // 如果状态变量的值为0，再次尝试CAS更新状态变量的值
                // 相对于公平锁模式少了!hasQueuedPredecessors()条件
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0) {
                    throw new Error("Maximum lock count exceeded");
                }
                setState(nextc);
                return true;
            }
            return false;
        }

        @Override
        protected final boolean tryRelease(int releases) {
            int c = getState() - releases;
            // 如果当前线程不是占有着锁的线程，抛出异常
            if (Thread.currentThread() != getExclusiveOwnerThread()) {
                throw new IllegalMonitorStateException();
            }
            boolean free = false;
            // 如果状态变量的值为0了，说明完全释放了锁
            // 这也就是为什么重入锁调用了多少次lock()就要调用多少次unlock()的原因
            // 如果不这样做，会导致锁不会完全释放，别的线程永远无法获取到锁
            if (c == 0) {
                free = true;
                // 清空占有线程
                setExclusiveOwnerThread(null);
            }
            // 设置状态变量的值
            setState(c);
            return free;
        }

        protected final boolean isHeldExclusively() {
            // While we must in general read state before owner,
            // we don't need to do so to check if current thread is owner
            return getExclusiveOwnerThread() == Thread.currentThread();
        }

        final ConditionObject newCondition() {
            return new ConditionObject();
        }

        // Methods relayed from outer class

        final Thread getOwner() {
            return getState() == 0 ? null : getExclusiveOwnerThread();
        }

        final int getHoldCount() {
            return isHeldExclusively() ? getState() : 0;
        }

        final boolean isLocked() {
            return getState() != 0;
        }

        /**
         * Reconstitutes the instance from a stream (that is, deserializes it).
         */
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            s.defaultReadObject();
            setState(0); // reset to unlocked state
        }
    }

    /**
     * NonfairSync实现了Sync，主要用于非公平锁的获取；
     */
    static final class NonfairSync extends Sync {
        private static final long serialVersionUID = 7316153563782823691L;

        /**
         * 这个方法在公平锁模式下是直接调用的acquire(1);
         */
        @Override
        final void lock() {
            // 直接尝试CAS更新状态变量
            if (compareAndSetState(0, 1)) {
                // 如果更新成功，说明获取到锁，把当前线程设为独占线程
                setExclusiveOwnerThread(Thread.currentThread());
            } else {
                acquire(1);
            }
        }

        @Override
        protected final boolean tryAcquire(int acquires) {
            // 调用父类的方法
            return nonfairTryAcquire(acquires);
        }
    }

    /**
     * FairSync实现了Sync，主要用于公平锁的获取。
     */
    static final class FairSync extends Sync {
        private static final long serialVersionUID = -3000897897090466540L;

        @Override
        final void lock() {
            // 调用AQS的acquire()方法获取锁
            // 注意，这里传的值为1
            acquire(1);
        }

        /**
         * Fair version of tryAcquire.  Don't grant access unless
         * recursive call or no waiters or is first.
         */
        @Override
        protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();  // 当前线程
            // 查看当前状态变量的值
            int c = getState();
            // 如果状态变量的值为0，说明暂时还没有人占有锁
            if (c == 0) {
                // 如果没有其它线程在排队，那么当前线程尝试更新state的值为1
                // 如果成功了，则说明当前线程获取了锁
                if (!hasQueuedPredecessors() &&
                    compareAndSetState(0, acquires)) {

                    // 当前线程获取了锁，把自己设置到exclusiveOwnerThread变量中
                    // exclusiveOwnerThread是AQS的父类AbstractOwnableSynchronizer中提供的变量
                    setExclusiveOwnerThread(current);
                    // 返回true说明成功获取了锁
                    return true;
                }
            }
            // 如果当前线程本身就占有着锁，现在又尝试获取锁
            // 那么，直接让它获取锁并返回true
            else if (current == getExclusiveOwnerThread()) {
                // 状态变量state的值加1
                int nextc = c + acquires;
                // 如果溢出了，则报错
                if (nextc < 0) {
                    throw new Error("Maximum lock count exceeded");
                }
                // 设置到state中
                // 这里不需要CAS更新state
                // 因为当前线程占有着锁，其它线程只会CAS把state从0更新成1，是不会成功的
                // 所以不存在竞争，自然不需要使用CAS来更新
                setState(nextc);
                // 当线程获取锁成功
                return true;
            }
            // 当前线程尝试获取锁失败
            return false;
        }
    }

    /**
     * 默认构造方法，非公平锁
     * 1. 非公平模式效率比较高。
     * 2. 非公平模式会在一开始就尝试两次获取锁，如果当时正好state的值为0，它就会成功获取到锁，少了排队导致的阻塞/唤醒过程，并且减少了线程频繁的切换带来的性能损耗。
     * 3. 非公平模式有可能会导致一开始排队的线程一直获取不到锁，导致线程饿死。
     */
    public ReentrantLock() {
        sync = new NonfairSync();
    }

    /**
     * 自己可选择使用公平锁还是非公平锁
     */
    public ReentrantLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
    }

    /**
     * ReentrantLock#lock()
     * ->ReentrantLock.FairSync#lock() // 公平模式获取锁
     *     ->AbstractQueuedSynchronizer#acquire() // AQS的获取锁方法
     *         ->ReentrantLock.FairSync#tryAcquire() // 尝试获取锁
     *         ->AbstractQueuedSynchronizer#addWaiter()  // 添加到队列
     * 	    ->AbstractQueuedSynchronizer#enq()  // 入队
     *         ->AbstractQueuedSynchronizer#acquireQueued() // 里面有个for()循环，唤醒后再次尝试获取锁
     *             ->AbstractQueuedSynchronizer#shouldParkAfterFailedAcquire() // 检查是否要阻塞
     *             ->AbstractQueuedSynchronizer#parkAndCheckInterrupt()  // 真正阻塞的地方
     *
     * 1. 尝试获取锁，如果获取到了就直接返回了；
     * 2. 尝试获取锁失败，再调用addWaiter()构建新节点并把新节点入队；
     * 3. 然后调用acquireQueued()再次尝试获取锁，如果成功了，直接返回；
     * 4. 如果再次失败，再调用shouldParkAfterFailedAcquire()将节点的等待状态置为等待唤醒（SIGNAL）；
     * 5. 调用parkAndCheckInterrupt()阻塞当前线程；
     * 6. 如果被唤醒了，会继续在acquireQueued()的for()循环再次尝试获取锁，如果成功了就返回；
     * 7. 如果不成功，再次阻塞，重复（3）（4）（5）直到成功获取到锁。
     *
     * 相对于公平锁，非公平锁加锁的过程主要有两点不同：
     * 1. 一开始就尝试CAS更新状态变量state的值，如果成功了就获取到锁了；
     * 2. 在tryAcquire()的时候没有检查是否前面有排队的线程，直接上去获取锁才不管别人有没有排队呢；
     *
     * 总的来说，相对于公平锁，非公平锁在一开始就多了两次直接尝试获取锁的过程。
     */
    @Override
    public void lock() {
        // 调用的sync属性的lock()方法
        // 这里的sync是公平锁，所以是FairSync的实例
        sync.lock();
    }

    /**
     * 支持线程中断，
     * 它与lock()方法的主要区别在于lockInterruptibly()获取锁的时候如果线程中断了，会抛出一个异常，
     * 而lock()不会管线程是否中断都会一直尝试获取锁，获取锁之后把自己标记为已中断，继续执行自己的逻辑，后面也会正常释放锁。
     *
     * 线程中断，只是在线程上打一个中断标志，并不会对运行中的线程有什么影响，具体需要根据这个中断标志干些什么，用户自己去决定。
     */
    @Override
    public void lockInterruptibly() throws InterruptedException {
        sync.acquireInterruptibly(1);
    }

    /**
     * 尝试获取一次锁，成功了就返回true，没成功就返回false，不会继续尝试。
     *
     * tryLock()方法比较简单，直接以非公平的模式去尝试获取一次锁，
     * 获取到了或者锁本来就是当前线程占有着就返回true，否则返回false。
     */
    @Override
    public boolean tryLock() {
        // 直接调用Sync的nonfairTryAcquire()方法
        return sync.nonfairTryAcquire(1);
    }

    /**
     * 尝试获取锁，并等待一段时间，如果在这段时间内都没有获取到锁，就返回false。
     *
     * tryLock(long time, TimeUnit unit)方法在阻塞的时候加上阻塞时间，并且会随时检查是否到期，只要到期了没获取到锁就返回false。
     */
    @Override
    public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
        // 调用AQS中的方法
        return sync.tryAcquireNanos(1, unit.toNanos(timeout));
    }

    /**
     * 释放锁、
     * 1. 将state的值减1；
     * 2. 如果state减到了0，说明已经完全释放锁了，唤醒下一个等待着的节点；
     */
    @Override
    public void unlock() {
        sync.release(1);
    }

    /**
     * Returns a {@link Condition} instance for use with this
     * {@link Lock} instance.
     *
     * <p>The returned {@link Condition} instance supports the same
     * usages as do the {@link Object} monitor methods ({@link
     * Object#wait() wait}, {@link Object#notify notify}, and {@link
     * Object#notifyAll notifyAll}) when used with the built-in
     * monitor lock.
     *
     * <ul>
     *
     * <li>If this lock is not held when any of the {@link Condition}
     * {@linkplain Condition#await() waiting} or {@linkplain
     * Condition#signal signalling} methods are called, then an {@link
     * IllegalMonitorStateException} is thrown.
     *
     * <li>When the condition {@linkplain Condition#await() waiting}
     * methods are called the lock is released and, before they
     * return, the lock is reacquired and the lock hold count restored
     * to what it was when the method was called.
     *
     * <li>If a thread is {@linkplain Thread#interrupt interrupted}
     * while waiting then the wait will terminate, an {@link
     * InterruptedException} will be thrown, and the thread's
     * interrupted status will be cleared.
     *
     * <li> Waiting threads are signalled in FIFO order.
     *
     * <li>The ordering of lock reacquisition for threads returning
     * from waiting methods is the same as for threads initially
     * acquiring the lock, which is in the default case not specified,
     * but for <em>fair</em> locks favors those threads that have been
     * waiting the longest.
     *
     * </ul>
     *
     * @return the Condition object
     */
    public Condition newCondition() {
        return sync.newCondition();
    }

    /**
     * Queries the number of holds on this lock by the current thread.
     *
     * <p>A thread has a hold on a lock for each lock action that is not
     * matched by an unlock action.
     *
     * <p>The hold count information is typically only used for testing and
     * debugging purposes. For example, if a certain section of code should
     * not be entered with the lock already held then we can assert that
     * fact:
     *
     *  <pre> {@code
     * class X {
     *   ReentrantLock lock = new ReentrantLock();
     *   // ...
     *   public void m() {
     *     assert lock.getHoldCount() == 0;
     *     lock.lock();
     *     try {
     *       // ... method body
     *     } finally {
     *       lock.unlock();
     *     }
     *   }
     * }}</pre>
     *
     * @return the number of holds on this lock by the current thread,
     *         or zero if this lock is not held by the current thread
     */
    public int getHoldCount() {
        return sync.getHoldCount();
    }

    /**
     * Queries if this lock is held by the current thread.
     *
     * <p>Analogous to the {@link Thread#holdsLock(Object)} method for
     * built-in monitor locks, this method is typically used for
     * debugging and testing. For example, a method that should only be
     * called while a lock is held can assert that this is the case:
     *
     *  <pre> {@code
     * class X {
     *   ReentrantLock lock = new ReentrantLock();
     *   // ...
     *
     *   public void m() {
     *       assert lock.isHeldByCurrentThread();
     *       // ... method body
     *   }
     * }}</pre>
     *
     * <p>It can also be used to ensure that a reentrant lock is used
     * in a non-reentrant manner, for example:
     *
     *  <pre> {@code
     * class X {
     *   ReentrantLock lock = new ReentrantLock();
     *   // ...
     *
     *   public void m() {
     *       assert !lock.isHeldByCurrentThread();
     *       lock.lock();
     *       try {
     *           // ... method body
     *       } finally {
     *           lock.unlock();
     *       }
     *   }
     * }}</pre>
     *
     * @return {@code true} if current thread holds this lock and
     *         {@code false} otherwise
     */
    public boolean isHeldByCurrentThread() {
        return sync.isHeldExclusively();
    }

    /**
     * Queries if this lock is held by any thread. This method is
     * designed for use in monitoring of the system state,
     * not for synchronization control.
     *
     * @return {@code true} if any thread holds this lock and
     *         {@code false} otherwise
     */
    public boolean isLocked() {
        return sync.isLocked();
    }

    /**
     * Returns {@code true} if this lock has fairness set true.
     *
     * @return {@code true} if this lock has fairness set true
     */
    public final boolean isFair() {
        return sync instanceof FairSync;
    }

    /**
     * Returns the thread that currently owns this lock, or
     * {@code null} if not owned. When this method is called by a
     * thread that is not the owner, the return value reflects a
     * best-effort approximation of current lock status. For example,
     * the owner may be momentarily {@code null} even if there are
     * threads trying to acquire the lock but have not yet done so.
     * This method is designed to facilitate construction of
     * subclasses that provide more extensive lock monitoring
     * facilities.
     *
     * @return the owner, or {@code null} if not owned
     */
    protected Thread getOwner() {
        return sync.getOwner();
    }

    /**
     * Queries whether any threads are waiting to acquire this lock. Note that
     * because cancellations may occur at any time, a {@code true}
     * return does not guarantee that any other thread will ever
     * acquire this lock.  This method is designed primarily for use in
     * monitoring of the system state.
     *
     * @return {@code true} if there may be other threads waiting to
     *         acquire the lock
     */
    public final boolean hasQueuedThreads() {
        return sync.hasQueuedThreads();
    }

    /**
     * Queries whether the given thread is waiting to acquire this
     * lock. Note that because cancellations may occur at any time, a
     * {@code true} return does not guarantee that this thread
     * will ever acquire this lock.  This method is designed primarily for use
     * in monitoring of the system state.
     *
     * @param thread the thread
     * @return {@code true} if the given thread is queued waiting for this lock
     * @throws NullPointerException if the thread is null
     */
    public final boolean hasQueuedThread(Thread thread) {
        return sync.isQueued(thread);
    }

    /**
     * Returns an estimate of the number of threads waiting to
     * acquire this lock.  The value is only an estimate because the number of
     * threads may change dynamically while this method traverses
     * internal data structures.  This method is designed for use in
     * monitoring of the system state, not for synchronization
     * control.
     *
     * @return the estimated number of threads waiting for this lock
     */
    public final int getQueueLength() {
        return sync.getQueueLength();
    }

    /**
     * Returns a collection containing threads that may be waiting to
     * acquire this lock.  Because the actual set of threads may change
     * dynamically while constructing this result, the returned
     * collection is only a best-effort estimate.  The elements of the
     * returned collection are in no particular order.  This method is
     * designed to facilitate construction of subclasses that provide
     * more extensive monitoring facilities.
     *
     * @return the collection of threads
     */
    protected Collection<Thread> getQueuedThreads() {
        return sync.getQueuedThreads();
    }

    /**
     * Queries whether any threads are waiting on the given condition
     * associated with this lock. Note that because timeouts and
     * interrupts may occur at any time, a {@code true} return does
     * not guarantee that a future {@code signal} will awaken any
     * threads.  This method is designed primarily for use in
     * monitoring of the system state.
     *
     * @param condition the condition
     * @return {@code true} if there are any waiting threads
     * @throws IllegalMonitorStateException if this lock is not held
     * @throws IllegalArgumentException if the given condition is
     *         not associated with this lock
     * @throws NullPointerException if the condition is null
     */
    public boolean hasWaiters(Condition condition) {
        if (condition == null)
            throw new NullPointerException();
        if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject))
            throw new IllegalArgumentException("not owner");
        return sync.hasWaiters((AbstractQueuedSynchronizer.ConditionObject)condition);
    }

    /**
     * Returns an estimate of the number of threads waiting on the
     * given condition associated with this lock. Note that because
     * timeouts and interrupts may occur at any time, the estimate
     * serves only as an upper bound on the actual number of waiters.
     * This method is designed for use in monitoring of the system
     * state, not for synchronization control.
     *
     * @param condition the condition
     * @return the estimated number of waiting threads
     * @throws IllegalMonitorStateException if this lock is not held
     * @throws IllegalArgumentException if the given condition is
     *         not associated with this lock
     * @throws NullPointerException if the condition is null
     */
    public int getWaitQueueLength(Condition condition) {
        if (condition == null)
            throw new NullPointerException();
        if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject))
            throw new IllegalArgumentException("not owner");
        return sync.getWaitQueueLength((AbstractQueuedSynchronizer.ConditionObject)condition);
    }

    /**
     * Returns a collection containing those threads that may be
     * waiting on the given condition associated with this lock.
     * Because the actual set of threads may change dynamically while
     * constructing this result, the returned collection is only a
     * best-effort estimate. The elements of the returned collection
     * are in no particular order.  This method is designed to
     * facilitate construction of subclasses that provide more
     * extensive condition monitoring facilities.
     *
     * @param condition the condition
     * @return the collection of threads
     * @throws IllegalMonitorStateException if this lock is not held
     * @throws IllegalArgumentException if the given condition is
     *         not associated with this lock
     * @throws NullPointerException if the condition is null
     */
    protected Collection<Thread> getWaitingThreads(Condition condition) {
        if (condition == null)
            throw new NullPointerException();
        if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject))
            throw new IllegalArgumentException("not owner");
        return sync.getWaitingThreads((AbstractQueuedSynchronizer.ConditionObject)condition);
    }

    /**
     * Returns a string identifying this lock, as well as its lock state.
     * The state, in brackets, includes either the String {@code "Unlocked"}
     * or the String {@code "Locked by"} followed by the
     * {@linkplain Thread#getName name} of the owning thread.
     *
     * @return a string identifying this lock, as well as its lock state
     */
    public String toString() {
        Thread o = sync.getOwner();
        return super.toString() + ((o == null) ?
                                   "[Unlocked]" :
                                   "[Locked by thread " + o.getName() + "]");
    }
}
